package mo.leetcode_top;

import mo.common.TreeNode;

public class L124 {

    private int res = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        helper(root, res);
        return res;
    }

    private int helper(TreeNode node, int r) {
        if (node == null) {
            return 0;
        }
        int left = Math.max(helper(node.left, r), 0);
        int right = Math.max(helper(node.right, r), 0);
        res = Math.max(res, left + right + node.val);
        return Math.max(left, right) + node.val;
    }

    public static void main(String[] args) {
        L124 test = new L124();
        TreeNode node = new TreeNode(-10);
        node.left = new TreeNode(9);
        node.right = new TreeNode(20);
        node.right.left = new TreeNode(15);
        node.right.right = new TreeNode(7);
        System.out.println(test.maxPathSum(node));
    }

}
